package exp4.test3;

/**
 * Created by 春旺 on 2017/11/23.
 */
public class Net {
    static int M=10000;//(此路不通)
    public static int[] Dijsktra(int[][] weight,int startVex){
        //顶点个数
        int count = weight.length;
        int[] shortestPath = new int[count];    //存放从start到其他各点的最短路径
        String[] path=new String[count]; //存放从start到其他各点的最短路径的字符串表示
        for(int i=0;i<count;i++)
            path[i]=new String(startVex+"-->"+i);
        int[] visited = new int[count];   //标记当前该顶点的最短路径是否已经求出,1表示已求出
        //初始化，第一个顶点求出
        shortestPath[startVex] = 0;
        visited[startVex] = 1;
        for(int ai = 1;ai <= count - 1;ai++)  //要加入n-1个顶点
        {
            int k = -1;    //选出一个距离初始顶点start最近的未标记顶点
            int dmin = Integer.MAX_VALUE;
            for(int i = 0;i < count;i++)
            {
                if(visited[i] == 0 && weight[startVex][i] < dmin)//没有标记过的顶点
                {
                    dmin = weight[startVex][i]; // 获取权值
                    k = i;
                }
            }
            //将新选出的顶点标记为已求出最短路径，且到start的最短路径就是dmin
            shortestPath[k] = dmin;
            visited[k] = 1;
            //以k为中间点，修正从start到未访问各点的距离
            for(int i = 0;i < count;i++)
            {
                if(visited[i] == 0 && weight[startVex][k] + weight[k][i] < weight[startVex][i]){
                    weight[startVex][i] = weight[startVex][k] + weight[k][i];
                    path[i]=path[k]+"-->"+i;
                }
            }
        }
        return shortestPath;
    }
}
